package demo4;

class TreeNodep {
    public int val;
    public TreeNodep left;
    public TreeNodep right;
    public TreeNodep(int ch) {
        this.val = ch;
    }
}
class Solution {
    int preIndex = 0;
    private TreeNodep createTreeBypandI (int[] postorder, int[] inorder, int inbegin, int inend) {
        if (inbegin > inend) {
            return null;
        }
        TreeNodep root = new TreeNodep(postorder[preIndex]);
        int rootIndex = findIndexOfI(inorder,inbegin,inend,postorder[preIndex]);
        preIndex--;

        root.right = createTreeBypandI(postorder,inorder,rootIndex + 1, inend);
        root.left = createTreeBypandI(postorder,inorder,0,rootIndex - 1);
        return root;
    }
    private int findIndexOfI (int[] inorder, int inbegin, int inend, int key) {
        for (int i = inbegin; i <= inend; i++) {
            if (inorder[i] == key) {
                return i;
            }
        }
        return -1;
    }
    public TreeNodep buildTree(int[] preorder, int[] inorder) {
        if (preorder == null || inorder == null) {
            return null;
        }
        preIndex = preorder.length - 1;
        return createTreeBypandI(preorder,inorder,0,inorder.length - 1);
    }
}
